12.2 Networks (Graphs)

149

where x comma yx, y, and zz are any three nodes and dd is the distance between a pair of nodes.

Trees are especially useful for representing hierarchical systems. The clustering

coefficient of a tree equals zero.

The complexity script upper CC of a tree T consisting of bb subtrees TSubscript 1 Baseline comma ellipsis comma normal upper T Subscript b Baseline1, . . . , Tb (i.e., bb is the

number of branches at the root), of which kk are not isomorphic, is defined as ¹⁶

script upper C equals script upper D minus 1 commaC = D −1 ,

(12.19)

where the diversity measurescript upper DD counts both interactions between subtrees and within

them and is given by

script upper D equals left parenthesis 2 Superscript k Baseline minus 1 right parenthesis product Underscript j equals 1 Overscript k Endscripts script upper D left parenthesis upper T Subscript j Superscript left parenthesis i right parenthesis Baseline right parenthesis periodD = (2^k −1)

kΠ

j=1

D(T⁽ⁱ⁾

j ^{) .}

(12.20)

If a tree has no subtrees,script upper D equals 1D = 1; the complexity of this, the simplest kind of tree, is set

to zero (hence, Eq. 12.19). Any tree with a constant branching ratio at each mode will

also havescript upper D equals 1D = 1 and, hence, zero complexity. This complexity measure satisfies the

intuitive notion that the most complex structures are intermediate between regular

and random ones (cf. Sect. 11.5).

12.2.2

Complexity Parameters of Networks

There are various measures of network complexity:

1. . κ, the number of different spanning trees of the network

2. Structural complexity, the number of parameters needed to define the graph

3. Edge complexity, the variability of the second shortest path between two nodes

4. Network or betaβ-complexity, given by the ratio German upper C divided by upper LC/L

5. Algorithmic complexity, the length of the shortest algorithm needed to describe

the network (see also Chap. 11).

12.2.3

Dynamical Properties

The essential concepts of physical structure and state structure were already intro-

duced in Sect. 12.1.1 and Fig. 12.1. A considerable body of work has been accom-

plished along these lines: investigating the state structures of simple, or simply con-

structed, networks. Kauffman, in particular, has studied large randomly connected

Boolean networks, with the interesting result that if each node has on average two

inputs from other nodes; typically, the state structure comprises about upper N Superscript 1 divided by 2N ^1/2 cyclic

16 See Huberman and Hogg (1986).